package com.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
 * <p>
 * 如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
 * <p>
 * 现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入: 10
 * 输出: 4
 * 解释:
 * 在[1, 10]中有四个好数： 2, 5, 6, 9。
 * 注意 1 和 10 不是好数, 因为他们在旋转之后不变。
 *  
 * <p>
 * 提示：
 * <p>
 * N 的取值范围是 [1, 10000]。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/rotated-digits
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class M_rotatesDigits {

    public static void main(String[] args) {
        int i = rotatedDigits(19);
        System.out.println(i);
    }

    private static int[] a = new int[6];
    private static int[][] dp = new int[6][2];

    public static int rotatedDigits(int n) {


        // return force(n);


        // return method1(n);

        // 官方暴力破解
        // return force_author(n);


        while (n != 0) {
            digits.add(n % 10);
            n /= 10;
        }
        Collections.reverse(digits);

        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 2; ++j) {
                Arrays.fill(memo[i][j], -1);
            }
        }

        return dfs1(0, 1, 0);

    }

    static int[] check = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
    static int[][][] memo = new int[5][2][2];
    static List<Integer> digits = new ArrayList<>();

    public static int dfs1(int pos, int bound, int diff) {
        if (pos == digits.size()) {
            return diff;
        }
        if (memo[pos][bound][diff] != -1) {
            return memo[pos][bound][diff];
        }

        int ret = 0;
        for (int i = 0; i <= (bound != 0 ? digits.get(pos) : 9); ++i) {
            if (check[i] != -1) {
                ret += dfs1(pos + 1, bound != 0 && i == digits.get(pos) ? 1 : 0, diff != 0 || check[i] == 1 ? 1 : 0);
            }
        }
        return memo[pos][bound][diff] = ret;
    }


    private static int force_author(int n) {
        int[] check = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            char[] num = String.valueOf(i).toCharArray();
            boolean valid = true, diff = false;
            for (char ch : num) {
                if (check[ch - '0'] == -1) {
                    valid = false;
                } else if (check[ch - '0'] == 1) {
                    diff = true;
                }
            }
            if (valid && diff) {
                ++ans;
            }
        }
        return ans;
    }

    private static int force(int n) {
        int[] check = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
        int sum = 0;

        // 暴力破解
        for (int i = 0; i <= n; i++) {
            int length = String.valueOf(i).length();
            int[] bits = new int[length];
            int i1 = i;
            for (int k = 0; k < length; k++) {
                bits[k] = i1 % 10;
                i1 /= 10;
            }
            if (length == 1 && check[i] == 1) {
                sum += 1;
            }
            if (length >= 2) {
                boolean isSub_1 = false;
                boolean isAdd_1 = false;
                for (int j = 0; j < length; j++) {
                    if (check[bits[j]] == -1) {
                        isSub_1 = true;
                    }
                    if (check[bits[j]] == 1) {
                        isAdd_1 = true;
                    }
                }
                if (isAdd_1 && !isSub_1) {
                    sum += 1;
                }
            }
        }

        return sum;
    }

    private static int method1(int n) {
        int len = 0;
        for (int[] e : dp) {
            Arrays.fill(e, -1);
        }
        while (n > 0) {
            a[++len] = n % 10;
            n /= 10;
        }
        return dfs(len, 0, true);
    }

    private static int dfs(int pos, int ok, boolean limit) {
        if (pos <= 0) {
            return ok;
        }
        if (!limit && dp[pos][ok] != -1) {
            return dp[pos][ok];
        }
        int up = limit ? a[pos] : 9;
        int ans = 0;
        for (int i = 0; i <= up; ++i) {
            if (i == 0 || i == 1 || i == 8) {
                ans += dfs(pos - 1, ok, limit && i == up);
            }
            if (i == 2 || i == 5 || i == 6 || i == 9) {
                ans += dfs(pos - 1, 1, limit && i == up);
            }
        }
        if (!limit) {
            dp[pos][ok] = ans;
        }
        return ans;
    }

}
